package edu.gatech.cs4235.group3;



import java.util.ArrayList;
import java.util.Arrays;
import org.apache.commons.math.MathException;
import org.apache.commons.math.stat.inference.TestUtils;
public class Cracker 
{
	
	private class spaceChart implements Comparable<spaceChart>{
		char character;
		Integer count;
		
		public spaceChart(char me){
			this.character = me;
			count = 0;
		}
		
		public int compareTo(spaceChart other){
			if(other.count>count) return 1;
			else if (other.count==count) return 0;
			else return -1;
		}
	}
	private static final int[] refFreqCounts = new int[]
	{
		0,
		114885	,
		834874	,
		80032	,
		68692	,
		157567	,
		0	,
		1236346	,
		1327970	,
		1317735	,
		125172	,
		85844	,
		3715463	,
		1976907	,
		5463442	,
		1372274	,
		2992049	,
		2489568	,
		1895810	,
		1349567	,
		1180848	,
		987562	,
		933907	,
		813163	,
		942763	,
		1530972	,
		1026536	,
		2110713	,
		0	,
		682232	,
		80312	,
		127339	,
		93952	,
		2096460	,
		792183	,
		2008465	,
		1041221	,
		1374610	,
		972045	,
		657129	,
		766949	,
		1608891	,
		384886	,
		230585	,
		1011778	,
		1273824	,
		1056903	,
		871538	,
		1267282	,
		84295	,
		1159352	,
		2223992	,
		2206398	,
		682233	,
		294651	,
		737606	,
		121129	,
		203967	,
		48504	,
		205016	,
		14765	,
		197878	,
		5004	,
		745553	,
		17067	,
		23011348	,
		3830737	,
		10507548	,
		10739084	,
		36746446	,
		6203070	,
		5726363	,
		11182850	,
		22890112	,
		440409	,
		1615729	,
		11893338	,
		8046264	,
		21777156	,
		22655503	,
		6592048	,
		358709	,
		19647971	,
		19065556	,
		26546777	,
		8930083	,
		3270139	,
		3806197	,
		865179	,
		4547936	,
		386941	,
		120400	,
		390137	,
		135636	,
		11019	,
	};
	
	private spaceChart[] spaceChars;
	
	/**
	 * @param cipherTexts Iterable of ciphertexts
	 * @return cracked pad
	 */
	public char[][][] crackMany(Iterable<char[][]> cipherTexts){
		//System.out.println("Go Go Crack");
		//We want to format this so we can pass the cipherTexts to the crackOne
		//Need to parse up the cipherTexts for their indie ciphers, throw those into the crackOne and save the keys.
		
		//need to hold all key arrays from the 16-1 cipher tries.
		ArrayList<char[][][]> allKeys = new ArrayList<char[][][]>();
		for(int i=1;i<17;i++){//i is Amount of keys being tried currently
			int count = 0;
			//System.out.println("Key Amount: "+i);
			char[][][] keys = new char[i][50][80];//Setting up the amount of pads for selected i
			ArrayList<ArrayList<char[][]>> splitCiphs = new ArrayList<ArrayList<char[][]>>();
			for(int j=0;j<i;j++){
				splitCiphs.add(new ArrayList<char[][]>());//Add enough cipher entries to accomodate the amount of pads
			}
			for(char[][] cipherText : cipherTexts) {
				splitCiphs.get(count%(i)).add(cipherText);//Add text to cipher entries in round robin state
				count++;
			}//Now all the cipherTexts have been placed into the splitCiphers at a 
			//List<char[][]> allTexts = new ArrayList<char[][]>();
			//char[][][][] splitCiphers = new char[modNum][][50][80];
			
			count = 0;
			for(int l=0;l<i;l++) {
				keys[l] = crackOne(splitCiphs.get(l));//analyze each possible pad
				if(keys[l]==null) {break;}//if the pad is shit, toss it
				else{count++;}
				if(count==i) { allKeys.add(keys);}
			}
		}
		int count = 0;
		double[] hitKeys= new double[allKeys.size()];//Will hold how many keys were not guessed
		for(char[][][] key : allKeys){//goes through each set of set of keys
			for(int i = 0;i<key.length;i++){
				for(int j=0;j<50;j++){
					for(int k=0;k<80;k++){
						if(key[i][j][k] >= 32 && key[i][j][k] <= 128){
							hitKeys[count]++;
						}
					}
				}
			}
			hitKeys[count] =hitKeys[count] /  (key.length*4000);
			count++;
		}
		//for(int i=0;i<hitKeys.length;i++){
		//	System.out.println("hitKeys["+i+"] = "+hitKeys[i]+" / #OTP");
		//}
		double val = 1; int index = 0;
		for(int i=0;i<hitKeys.length;i++){
			//System.out.println("a: "+val);
			if(Math.abs(1-hitKeys[i]) <= val ){
				//System.out.println(Math.abs(1-hitKeys[i])+" "+i);
				val = Math.abs(1-hitKeys[i]);
				index = i;
			}
		}
		return allKeys.get(index);
	}
	/*
		for(int i=15;i<=0;i--){//Master for loop, makes i keys	//Assume 16 ciphertexts, then 15 etc
			char[][][] key = new char[i][50][80];
			for(int j=0;j<50;j++){//Make the last col of all 50 rows
				for(int k=0;k<i;k++){//for all ciphers 0-i
					key[k][j][79] = (char)' ';
				}
			}//Spaces are made
			
		
		return null;
	}
	*/
	
	
	
	
	
	public char[][] crackOne(Iterable<char[][]> cipherTexts) 
	{
		int[][][] fCounts = new int[50][80][95];//Maintain the frequency charts for each spot in the key


		char[][] key = new char[50][80];
		
		for(int x = 0; x < 50; x++)
		{
			key[x][79] = ' ';//Put those spaces in
		}
		int crackedChars = 50;//For the last line of all spaces
		//We want to get some data about the kind of characters we'll find, using the last column of which we know the key
		//In this way we can
		spaceChars = new spaceChart[95];
		for(int i=0;i<95;i++) {
			spaceChars[i]=new spaceChart((char)(i+32));
		}
		//int k = 0;
		//Fill in the freq data for the space column into spaceChars
		for(char[][] cipherText : cipherTexts) {
			//k++;
			//System.out.println(cipherText+"K: "+k);
			for(int i = 0; i < 50; i++)
			{ 
				//System.out.println("i: "+i);
				spaceChars[(cipherText[i][79])-32].count++;
			}
		}
		//Sort the data we got from the space coluumn
		Arrays.sort(spaceChars);
		
		int ciphs = 0;
		for(char[][] cipherText : cipherTexts)
		{
			if(ciphs >1000 && crackedChars < 1000){return null;}
			for(int x = 0; x < 50; x++){
				for(int y = 0; y < 79; y++){
					if(key[x][y] == 0){//For all x,y check if the key has been found, if not add the ciphertext to the appropriate freqchart and see if
						//there is enough data to guess the key
						if(ciphs%500==0){ fCounts[x][y] = new int[95];}
						fCounts[x][y][cipherText[x][y] - 32]++;
						Byte keyBit = null;
						//Check for found characters using Chi Squared Test
						if(ciphs%800==0) {//Only check every 50 cipherTexts, to speed it up as youll get a ton of false anyway at low ciphertexts
							keyBit = descrambleAndCheck(fCounts[x][y],spaceChars[0].character,0.0000000000000000000000000000000001);
						}
						if(keyBit != null)
						{
							crackedChars++;
							key[x][y] = (char)keyBit.byteValue();
						}
					}
				}
			}
			if(crackedChars>=4000) break;

			
			ciphs++;
		}
		//System.out.println("One CT Done");
		return key;
	}
	
	private Byte descrambleAndCheck(int[] ciFC,char guess,double alpha)
	{		
		int indexCommon = 0;
		int valueCommon = 0;
		for(int i = 0; i < 95; i++){//Go through the freq table and find the most common letter
			if(ciFC[i] > valueCommon){
				indexCommon = i;valueCommon = ciFC[i];
			}
		}
		int keyDiff = indexCommon - ((int)guess - 32);
		if(keyDiff < 0){
			keyDiff += 95;
		}
		keyDiff %= 95;
		byte key = (byte)(keyDiff + 32);
		int plainSum = 0;
		long[] pFC = new long[95];
		for(int i = 0; i < 95; i++){
			pFC[i] = ciFC[(i + keyDiff) % 95];
			plainSum += pFC[i];
		}
		double[] expectedShort = new double[26];
		long[] observedShort = new long[26];
		int lowerCaseSum = 0;
		int lowerCaseSumObs = 0;
				
		for(int g=0;g<26;g++) {
			observedShort[g] = pFC[65+g];
			lowerCaseSum+=refFreqCounts[65+g];
			lowerCaseSumObs+=observedShort[g];
		}
		for(int g=0;g<26;g++) {
			expectedShort[g] = ((refFreqCounts[65+g]/(double)lowerCaseSum) * lowerCaseSumObs);
			//if(observedShort[g]==0) {System.out.println((char)(g+97));}
			if(expectedShort[g]==0) return null;

		}
		boolean test=false;
		try {
			test = TestUtils.chiSquareTest(expectedShort,observedShort,alpha);
		} catch (IllegalArgumentException e) {
			e.printStackTrace();
		} catch (MathException e) {
			e.printStackTrace();
		}
		if(test){
			return null;}
		else{
			return key;}
		
	}

}
